home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
The X-Philes (2nd Revision)
/
The X-Philes Number 1 (1995).iso
/
xphiles
/
hp48_2
/
obj.pos
< prev
next >
Wrap
Text File
|
1995-03-23
|
7KB
|
162 lines
Article 1853 of comp.sys.handhelds:
Path: en.ecn.purdue.edu!pur-ee!mentor.cc.purdue.edu!purdue!tut.cis.ohio-state.edu!snorkelwacker!usc!elroy.jpl.nasa.gov!jarthur!nntp-server.caltech.edu!piglet!madler
From: madler@piglet.caltech.edu (Mark Adler)
Newsgroups: comp.sys.handhelds
Subject: Re: My last post on sorting (sure) for the HP-48SX
Message-ID: <1990Apr16.194958.22624@laguna.ccsf.caltech.edu>
Date: 16 Apr 90 19:49:58 GMT
References: <1990Apr11.045126.5737@laguna.ccsf.caltech.edu> <54098@microsoft.UUCP>
Sender: news@laguna.ccsf.caltech.edu
Organization: California Institute of Technology, Pasadena
Lines: 147
Oops on OPOS. Here is a corrected version of OPOS---the last one
didn't work for elements that belonged on the end of the list.
Also included here is an improved QPART using Alonzo's code for
swapping [i] and [j] more efficiently. (I see that Alonzo can't
resist small tweaks either.)
Mark Adler
madler@tybalt.caltech.edu
%%HP: T(3)A(R)F(.);
@ OPOS crc #DEh length 142
@
@ by Mark Adler 16 Apr 1990
@
@ Ordered POS: the arguments are a list in level 2 and the element to
@ locate in level 1. The result is the location in level 2 and a
@ boolean in level 1 which is true if the element is in the list. The
@ location has the range 1..n+1, where n is the number of entries in
@ the list. n+1 indicates the element belongs at the end of the list
@ (the boolean is always false in this case). It is assumed that the
@ input list is ordered so that the first entry is less than or equal
@ to the second entry, the second is less than or equal to the third,
@ etc.
@
@ OPOS uses SRCH to find where in the list the element goes. SRCH
@ uses the ">" operation to compare elements, but this can be changed
@ in SRCH---see the comments in SRCH. The ">" in this routine would
@ also have to be changed in the same way.
@
\<<
SWAP OBJ\-> \-> n
\<<
n 1 + ROLL n SRCH @ do search
3 - \-> k j @ save k, index
\<<
IF j DUP THEN @ if j not past end,
PICK k > NOT @ see if k in list
END
n 1 + ROLLD n DROPN @ trash list
n j - 1 + @ compute location
SWAP @ return index, boolean
\>>
\>>
\>>
%%HP: T(3)A(R)F(.);
@ QPART crc #156h length 412
@
@ by Mark Adler 16 Apr 1990
@
@ Given a partition of the stack, pick an entry in the partition and
@ split the partition into two partitions such that all the entries in
@ the first one are less than the entry picked, and all the entries in
@ the second one are greater than the entry picked, and the entry is
@ placed between them. Then call this routine recursively for each of
@ those partitions, unless the partition is 20 entries or less. A
@ final pass of an insertion sort should be done to sort the remaining
@ short partitions. The value of 20 was determined experimentally on
@ test cases of lists of random reals.
@
@ The entry for partitioning is picked using the median method, which
@ picks the median value of the entries at the beginning, middle, and
@ end of the list. This makes the sort fast for already sorted lists,
@ and greatly reduces the probability of the sort taking order n^2
@ time. It also reduces the total number of comparisons, speeding the
@ sort somewhat. Most importantly, an additional step of sorting the
@ first and last elements of the list (which adds one compare) allows
@ the inner loops of the algorithm to not have to check for the bounds
@ of the partition. This special-purpose three element sort does not
@ cost extra, since the outer two elements would have to have been
@ compared and swapped anyway if they were in the wrong place. Thanks
@ to Alonzo Gariepy for an improved swap of [i] and [j].
@
@ The arguments to QPART are two integers specifying the stack levels
@ to partition. The arguments refer to the stack after the arguments
@ are removed from the stack. The integer in the first level minus 1
@ is the starting level, and the integer in level 2 is the ending level
@ to partition. So, for example, to partition the stack levels 1
@ through n, the calling sequence would be "n 2 QPART". Since QPART
@ does not check the partition size on entry, the calling routine
@ should do that and avoid calling QPART for sizes of 20 or less.
@
@ The algorithm can be modified to sort objects besides reals and
@ strings by replacing the ">" in the "IF DUP2 >"'s and in the "PICK >"
@ and replacing the "<" in the "PICK <" with the appropriate code for
@ the object. The routine can be generalized (at a speed penalty) by
@ replacing said ">"'s with "GT" and the said "<" with "SWAP GT" and
@ defining a function "GT" that does the job before doing the sort.
@
\<<
@ sort the partition of the stack from level l-1 to level r (after
@ l and r are pulled off of the stack).
\-> r l \<<
@
@ sort [l-1], [m], [r] so that [l-1] >= [m] >= [r] where m points
@ to the middle of the partition.
@
r l + 2 / FLOOR ROLL @ get [m]
l ROLL @ get [l-1]
IF DUP2 > THEN SWAP END @ sort [m], [l-1]
l ROLLD r ROLL @ put back new [l-1]; get [r]
IF DUP2 > THEN @ if [r], [m] sorted,
r @ then just put [r] back
ELSE
SWAP r ROLLD l ROLL @ else sort [r], [m]; get [l-1]
IF DUP2 > THEN SWAP END @ and re-sort [m] and [l-1]
l @ put [l-1] back
END
ROLLD
@
@ start sorting inside [l-1], [r] since [l-1] and [r] are already
@ sorted. put [m] in list so that [i] >= [m] >= [j] for i < j.
@
r 3 + SWAP @ i = l-1 (loop begins "1 +")
l 3 + @ j = r-1 (since m pulled out)
WHILE @ stack is i+4,[m],j+4,list...
WHILE 1 + DUP2 PICK < REPEAT END @ now [m] >= [i]
SWAP ROT
WHILE 1 - DUP2 PICK > REPEAT END @ now [j] >= [m]
ROT DUP2 > @ until j <= i
REPEAT @ stack is i+4,j+4,[m],list...
DUP2 SWAP ROLL SWAP ROLLD @ swap [i] and [j]
DUP2 ROLL OVER ROLLD
DROP ROT SWAP @ stack is i+4,[m],j+4,list...
END
DROP 2 - SWAP OVER ROLLD @ put [m] after [j]
@
@ sort the partitions [j+2..r] and [l-1..j] by calling this program
@ recursively, but only if the partition has length > 20. The
@ stack is j+2,list...
@
IF r DUP2 - -18 < THEN @ check top partition
SWAP DUP 'r' STO 1 + QPART r @ save j+2 in r
ELSE
DROP
END @ j+2 left on stack
IF 2 - l DUP2 - 18 > THEN @ check bottom partition
QPART
ELSE
DROP2
END @ leave the list on the stack
\>>
\>>